package listbyorder.access301_400.test322;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution3 {

    int ans = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        // 将int型数组包装成Integer型数组，便于使用JavaAPI进行排序
        Integer[] ib = IntStream.of(coins).boxed().collect(Collectors.toList()).toArray(new Integer[0]);
        Arrays.sort(ib, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        // dfs进行更新操作
        dfs(ib, amount, 0, 0);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private void dfs(Integer[] coins, int amount, int c_index, int count) {
        if (amount == 0) {
            ans = Math.min(ans, count);
            return;
        }
        if (c_index == coins.length) return;
        // 一次走多行
        for (int i = amount / coins[c_index]; i >= 0 && i + count < ans; i--) {
            dfs(coins, amount - (i * coins[c_index]), c_index + 1, count + i);
        }
    }
}
